package leetcode.Fiftyone_to_One_hundred;

/**
 * 矩阵置零
 */
public class Test73 {

    public static void setZeroes(int[][] matrix) {
        if (matrix.length == 0) {
            return;
        }
        boolean firstRowIsZero = false, firstColIsZero = false;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {

                // 若不是第一行第一列的元素为 0，则将其对应的第一行第一列对应的元素设为 0
                if (i != 0 && j != 0 && matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                } else if (matrix[i][j] == 0) {
                    // 判断 i、j 哪个是 0
                    firstRowIsZero = i == 0 ? true : firstRowIsZero;
                    firstColIsZero = j == 0 ? true : firstColIsZero;
                }
            }
        }

        /**
         * 为什么选择从 1 开始，
         * 因为0行、0列已经用来标记当前行或者当前列是否存在0了
         * 只需要将标记的行、列的剩余元素置0即可
         */
        for (int i = 1; i < matrix.length; i++) {
            for (int j = 1; j < matrix[0].length; j++) {
                /**
                 * 如果遇到第i行、第j列的第一个元素标记为0的
                 * 将此列、行的当前扫描到的元素置为0
                 */
                if (matrix[0][j] == 0 || matrix[i][0] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }

        //第一列含 0
        if (firstColIsZero) {
            for (int i = 0; i < matrix.length; i++) {
                matrix[i][0] = 0;
            }
        }
        //第一行含 0
        if (firstRowIsZero) {
            for (int j = 0; j < matrix[0].length; j++) {
                matrix[0][j] = 0;
            }
        }
    }

    public static void main(String[] args) {
//        int[][] a = {{1, 1, 1}, {1, 0, 1}, {1, 1, 1}};
        int[][] a = {{0, 1, 0}, {1, 1, 1}, {0, 1, 0}};

        setZeroes(a);

        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a[0].length; j++) {
                System.out.print(a[i][j] + " ");
            }
            System.out.println();
        }
    }
}
